import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class TestSort {
    public static void insertSort(int[] array){
        //进行对数组的遍历
        for (int i = 1; i < array.length; i++) {
            //暂存节点，取出第二个节点
            int tmp=array[i];
            //排序节点，对新插入的节点进行排序
            int j = i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    //array[j+1]=tmp;//只要j回退的时候，遇到了比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了小于0的地方的情况
            array[j+1]=tmp;//每次的调换都是相邻的数据进行交换，将暂取值放回原位，没有跳跃式的调换
        }
    }

    public static void shell(int[] array,int gap){
        //从下标为1的元素开始进行遍历
        for (int i = gap; i < array.length; i++) {
            //暂取下标为1的元素
            int tmp=array[i];
            //进行升序的排序，以选择排序为基础，这次进行跳跃排序，根据正态分布，间隔变大，两极分化的概率变大，提高排序的可能性，记录分组的前一个位置
            int j=i-gap;

            for (; j >=0 ; j-=gap) {
                //前后间隔数据进行比较，升序交换排列
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
            //后数大于前数的时候，排序不变，将暂取值放回原位或者跳跃赋值，也体现插入排序的不稳定性
            array[j+gap]=tmp;
        }

    }

    public static void shellSort(int[] array){
        //分组根据数组的长度为依据
        int gap=array.length;
        while (gap>1){
            //定义分组的方法
            shell(array,gap);
            gap/=2;
        }
        //一组的时候一定要进行最终的排序
        shell(array,1);
    }
    public static void swap(int[] arr, int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
public static void select(int[] array){
    for (int i = 0; i < array.length; i++) {
        for(int j=i+1;j<array.length;j++){
            if(array[j]>array[i]){
                swap(array,i,j);
        }
        }
    }
}
    public static void selectIndex(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=0;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;

                }
            }
            swap(array,i,minIndex);
        }
    }


    //时间复杂的为：o(N*log2N)
    //空间复杂的为：O1
    //稳定性：不稳定
    public static void heatSort(int[] array){
        //1.建堆 o(n)
        createHeat(array);
        int end=array.length-1;
        //2.交换后调整  o(n*log2N)
        while (end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void createHeat(int[] array){
        //创建一个大根堆
        for (int parent = (array.length-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    public static void shiftDown(int[] array,int parent,int len){
        int child=parent*2+1;//左孩子的下标
        //每一次都把从新的父节点的位置开始往下调整，保证数据为大根堆
        while (child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            //child下标存的值为左右孩子中的最大值
            if(array[child]>array[parent]){
                //如果孩子大于父亲的值交换父子的值，保证为大根堆
                swap(array,parent,child);
                //交换完之后，将孩子的值赋值给父亲节点，以子节点为父亲，重新进行查找交换，保证为大根堆
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //时间复杂的：o(n^2)
    //空间复杂的：o1
    //稳定性：稳定的排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                }
            }
        }

    }
    //时间复杂的：o(n^2)，最好的时候为o(n)
    //空间复杂的：o1
    //稳定性：稳定的排序
    public static void bubbleSort1(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(flg==false){
                break;
            }
        }
    }

    //时间复杂度：o(k*n*logn) （每次可以均匀的分割待排序的数据）
    //最坏情况：o(n^2) 数据有序或者逆序的时候
    //空间复杂度最好o(logn)
    //最坏情况下为单分支的树o(n)
    //稳定性：不稳定
    public static void quickSort1(int[] array){
        quick( array, 0, array.length-1);
    }
    public static void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //如果区间内的数据，在排序的过程中小于某个范围了，可以直接使用插入排序
        if(right-left+1<=40){
            insertSort(array);
            return;
        }

        //找基准之前先找到中间大小的值
        int midValIndex=findMidValIndex(array,left,right);
        swap(array,midValIndex,left);
        int pivot=partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    private static int findMidValIndex(int[] array,int start,int end){
        int mid=start+((end-start)>>>1);
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else {
                return mid;
            }
        }else {
            if(array[mid]>array[start]){
                return start;
            }else if(array[mid]<array[end]){
                return end;
            }else {
                return mid;
            }
        }
    }
    public static int partition(int[] array,int start,int end){
        int tmp=array[start];
        while (start<end){
            while (start<end&&array[end]>=tmp){
                end--;
            }
            //end下标遇到了小于tmp的值
            //升序排列，大的数值放到后面，小的数值放到前面
            array[start]=array[end];
            while (start<end&&array[start]<=tmp){
                start++;
            }
            //start下标遇到了大于tmp的值
            //升序排列，大的数值放到后面，小的数值放到前面
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }
    public static void quickSort(int[] array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);
        if(pivot>left+1){
            //左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot<right-1){
            //右边有两个元素
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition(array,left,right);
            if(pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }


    //归并排序
    //时间复杂度：N*log N
    //空间复杂的：N
    //稳定性：稳定的排序
    //如果array[s1]<=array[s2]  不取等号那么就是不稳定的排序
    //稳定的排序可以变成不稳定的排序，但是不稳定的排序不能变为稳定的排序
    //现阶段学过的排序只有三个是稳定的：冒泡、插入、归并   插入和归并的时间复杂度小一点
    public static int[] mergeArray1(int[] array1, int[] array2){
        if(array1==null&&array2==null){
            return null;
        }
        if(array1==null){
            return array2;
        }if(array2==null){
            return array1;
        }
        int len1=array1.length;
        int len2=array2.length;
        int[] tmp=new int[len1+len2];
         int i=0;
        int star1=0;
        int end1=len1-1;
        int star2=0;
        int end2=len1-1;
        while (star1<=end1&&star2<=end2){
            if(array1[star1]<array2[star2]){
                tmp[i++]=array1[star1++];

            }else {
                tmp[i++]=array2[star2++];

            }
        }
        while (star1<=end1){
            tmp[i++]=array1[star1++];
        }
        while (star2<=end2){
            tmp[i++]=array2[star2++];
        }
        return tmp;
    }

    public static void mergeSort(int[] array){
         mergeSortInternal(array,0,array.length-1);

    }
    private static void mergeSortInternal(int[] array,int low,int high){
        if(low>=high){
            return;
        }
        int mid=low+((high-low)>>>1);
        //左边
        mergeSortInternal(array,low,mid);
        //右边
        mergeSortInternal(array,mid+1,high);
        //合并
        merge(array,low,mid,high);

    }
    private static void merge(int[] array,int low,int mid,int high){
        int[] tmp=new int[high-low+1];
        int i=0;
        int star1=low;
        int end1=mid;
        int star2=mid+1;
        int end2=high;
        while (star1<=end1&&star2<=end2){
            if(array[star1]<array[star2]){
                tmp[i++]=array[star1++];

            }else {
                tmp[i++]=array[star2++];

            }
        }
        while (star1<=end1){
            tmp[i++]=array[star1++];
        }
        while (star2<=end2){
            tmp[i++]=array[star2++];
        }
        for (int j = 0; j < i; j++) {
            array[j+low]=tmp[j];

        }

    }
    //非递归实现归并排序

    public static void mergeSort2(int[] array){
        int nums=1;
        while (nums<array.length){
            //数组每次都要进行遍历,确定要归并的区间
            for (int i = 0; i < array.length; i+=nums*2) {
                int left=i;
                int mid=left+nums-1;
                //防止越界
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=mid+nums;
                if(right>=array.length){
                    right=array.length-1;
                }
                //下标确定之后，进行合并
                merge(array,left,mid,right);
            }
            nums*=2;
        }

    }
    //计数排序 有n个数，数据范围为0-n
    //时间复杂的：o(n)
    //空间复杂的：o（m） m为当前数据的范围900-999
    //稳定性：当前代码是不稳定，但是本质是稳定的
    public static void countingSort(int[] array){
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i]<minVal){
                minVal=array[i];
            }
            if(array[i]>maxVal){
                maxVal=array[i];
            }
        }
        //说明已经找到了最大值和最小值
        int[] count=new int[maxVal-minVal+1];
        //统计array数组当中每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int index=array[i];
            //为了空间的合理利用，这里需要index-minval  防止923-900
            count[index-minVal]++;
        }
       //说明在计数数组当中已经把array数组当中，每个数据出现的次数已经统计好了
        //接下来只需要遍历数组，开始把数组写回数组
        int indexArray=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                //这里一定加minval,因为不一定就是i出现了count[i]
                array[indexArray]=i+minVal;
                count[i]--;//拷贝一个数据之后，数据就减少一个
                indexArray++;//拷贝一个数据之后，数组的下标值就增加一个
            }
        }
    }

    public static void Test1(int capacity){
        int[] array=new int[capacity];
        for (int i = 0; i < array.length; i++) {
            array[i]=i;
        }
        long start=System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //select(array);
        heatSort(array);
        long end=System.currentTimeMillis();
        System.out.println(end-start);
    }
    public static void Test2(int capacity){
        int[] array=new int[capacity];
        Random random=new Random();

        for (int i = 0; i < array.length; i++) {
            array[i]=random.nextInt(capacity);
        }
        long start=System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //select(array);
        heatSort(array);
        long end=System.currentTimeMillis();
        System.out.println(end-start);
    }



    public static void main1(String[] args) {
        Test1(100000);
        Test2(100000);

    }
    public static void main(String[] args) {
        int[] arr={12,5,18,10,4,2};
       // shellSort(arr);
        //quickSort(arr);
        //mergeSort(arr);
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void main3(String[] args) {
        int[] array1={1,3,5,7,9};
        int[] array2={2,4,6,8,10};
        int[] ret=mergeArray1(array1,array2);
        System.out.println(Arrays.toString(ret));
    }
}
